package dfs;

import offer.Class04;

//TODO:2023/9/17 惩罚数
public class Class2698 {


        public int punishmentNumber(int n) {
            int ans = 0;
            for (int i = 1; i <= n; i++) {
                int t = i * i;
                if (dfs(t + "", 0, i)) {
                    ans += t;
                }
            }
            return ans;
        }



        private boolean dfs(String str, int index, int target) {
            if (index == str.length()) {
                return target == 0;
            }
            for (int i = index; i < str.length(); i++) {
                int curr = Integer.parseInt(str.substring(index, i + 1));
                // 减枝
                if (target - curr < 0) {
                    break;
                }
                if (dfs(str, i + 1, target - curr)) {
                    return true;
                }
            }
            return false;
        }


    public static void main(String[] args) {
        Class2698 class2698 = new Class2698();
        System.out.println(class2698.punishmentNumber(10));
    }



    }



